The following relates to the planning arts, predictive arts, scheduling arts, and related arts, and will find application in diverse fields such as for example equipment servicing, delivery services, robotic control, financial planning, and other fields entailing hybrid processes that are generally continuous but include occasional discrete events or discontinuities.
Stochastic control problems are relevant to numerous applications entailing modeling or other representation of a process that evolves over time (or with respect to another variable). In the 1960's various exact linear programming solution techniques were developed for such problems. These linear programming methods entail determining a value function indicative of the cost on the process of taking an action, constructing a constraint on the solution in the form of a linear combination, and optimizing the value function subject to the constraint. These exact linear programming solution techniques are computationally intensive and impractical for large state spaces, a problem sometimes referred to as the “curse of dimensionality.”
In the 1980's, techniques were developed to obtain linear programming solutions in an approximate manner. These techniques entail representing the value function as a linear combination of basis functions and optimizing the weights or coefficients of the linear combination of basis functions subject to the constraints also represented in terms of the linear combination of basis functions. In effect, the dimensionality is reduced from the number of states in the state space to the number of weights in the lower dimensional weight space. This variation of linear programming is known in the art as approximate linear programming (ALP).
ALP substantially enhances the applicability of linear programming to practical problems. However, ALP, and linear programming in general, has heretofore been applied to continuous processes (possibly represented by discrete time samples) in which the variation with respect to time (or another variable) is continuous and does not include jumps or abrupt transitions.
Adaptation of linear programming to planning, scheduling or to generally continuous processes with occasional discontinuities or abrupt changes would substantially increase the range of target planning and scheduling applications. For example, machine maintenance scheduling involves abrupt discontinuities respective to time generated by machines transitioning between states (e.g., from a working state to a failure state to an “under repair” state back to a working state). Some stock market modeling applications would also benefit from the ability to model rapid stock price transitions caused by discrete events (e.g., corporate announcements, major political events, or so forth) as abrupt jumps or transitions. Such processes which are generally continuous but include occasional jumps, discontinuities, or abrupt changes are sometimes called “hybrid” processes.
Heretofore, linear programming techniques have generally not been used in conjunction with hybrid processes having jumps or discontinuities. Conceptually, existing linear programming techniques involve searching a constrained continuous space to identify a vertex or other extremum corresponding to a constrained optimum value of the value function. It is not readily apparent that such linear programming techniques could be adapted to handle hybrid processes in which the value function has discontinuities within the searched space.